﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using KS.Utils;
using System.Diagnostics;
using System.Collections.Concurrent;

namespace KS
{
    public class KnightSequenceGenerator
    {

        #region Props

        public List<int> ValidSequenceLengths = new List<int>() { { 10 }, { 12 }, { 16 }, { 32 } };
        public int MaxSequenceLength { get; set; }
        public ConcurrentBag<string> Sequences { get; set; }
        public Object SequenceCountLock = new Object();
        public int SequenceCount { get; set; }
        public readonly int[,] KnightMoves = { { +1, -2 }, { +2, -1 }, { +2, +1 }, { +1, +2 }, { -1, +2 }, { -2, +1 }, { -2, -1 }, { -1, -2 } };
        public Key[,] KeyPad = new Key[4, 5] 
                               { 
                                   { new Key("A"),   new Key("B"), new Key("C"), new Key("D"), new Key("E") }, 
                                   { new Key("F"),   new Key("G"), new Key("H"), new Key("I"), new Key("J") },
                                   { new Key("K"),   new Key("L"), new Key("M"), new Key("N"), new Key("O") },
                                   { new Key(null),  new Key("1"), new Key("2"), new Key("3"), new Key(null) }
                               };

        public IEnumerable<Key> ValidKeys;

        #endregion


        static void Main(string[] args)
        {
            KnightSequenceGenerator ksGenerator = new KnightSequenceGenerator();

            #region Checks Args 10, 16 or 32
            if (args.Length != 1)
            {
                InvalidArgsMessageAndExit();
            }
            else
            {
                int inputVar;
                bool result = Int32.TryParse(args[0], out inputVar);
                if (result)
                {
                    ksGenerator.MaxSequenceLength = inputVar;
                    if (ksGenerator.MaxSequenceLength != 4 && ksGenerator.MaxSequenceLength != 10 && ksGenerator.MaxSequenceLength != 12 && ksGenerator.MaxSequenceLength != 16 && ksGenerator.MaxSequenceLength != 32)
                    {
                        InvalidArgsMessageAndExit();
                    }
                }
                else
                {
                    InvalidArgsMessageAndExit();
                }
            }
            #endregion

            // Initialize KeyPad
            ksGenerator.Init();

            // Generate Sequence
            ksGenerator.GenerateSequence();

        }


        private static void InvalidArgsMessageAndExit()
        {
            Console.WriteLine("Please Enter one of the following, 10, 16 or 32..." + Environment.NewLine + "Press any key to Exit...");
            Console.ReadLine();
            Environment.Exit(-1);
        }


        private void Init()
        {
            #region Init KeyPad Keys

            for (int i = 0; i < this.KeyPad.GetLength(0); i++)
            {
                for (int j = 0; j < this.KeyPad.GetLength(1); j++)
                {
                    this.KeyPad[i, j].NextLegalMoves = SetPossibleMoves(i, j);
                }
            }

            #endregion

            Sequences = new ConcurrentBag<string>();

            // Set Valid Keys
            ValidKeys = this.KeyPad.Cast<Key>().Where(k => k.Value != null);
        }


        public List<Key> SetPossibleMoves(int i, int j)
        {
            List<Key> nextLegalMoves = new List<Key>();

            if ((i == 3 && j == 0) || (i == 3 && j == 4)) { return null; } // Exist on struc beside 1 and 3

            for (int k = 0; k < this.KnightMoves.GetLength(0); k++)
            {
                int newRow = 0;
                int newCol = 0;
                newRow = (i + this.KnightMoves[k, 0]); newCol = (j + this.KnightMoves[k, 1]);


                if (newRow > 3 || newCol > 4 || newRow < 0 || newCol < 0 || (newRow == 3 && newCol == 0) || (newRow == 3 && newCol == 4))
                {
                    continue;
                }
                else
                {
                    Key newLegalKeyMove = this.KeyPad[newRow, newCol];
                    if (newLegalKeyMove.Value != null)
                    {
                        nextLegalMoves.Add(newLegalKeyMove);
                    }
                }
            }
            return nextLegalMoves;
        }


        private void GenerateSequence()
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            #region Create Structure to Traverse
            ConcurrentDictionary<string, List<Key>> struc = new ConcurrentDictionary<string, List<Key>>();
            foreach (Key key in ValidKeys) { struc.TryAdd(key.Value, key.NextLegalMoves); }
            #endregion

            Parallel.ForEach(struc, item => this.RecurseMoves(struc, 0, new StringBuilder(), item.Key));

            sw.Stop();

            Console.WriteLine("Count: " + this.SequenceCount + ", Calculation took: " + sw.Elapsed + Environment.NewLine + "Press any key to exit...");
            Console.ReadLine();

            #region Notes

            /* 
             * 
             * To use: Just enter debug param 10|16|32 if running from VS, otherwise from cmd line .\KS.exe 10
             * 
             * Times:
             *      10 char sequence - 1.03 sec
             *      12 char sequence - 18.03 sec (x18)
             *      so 
             *      16 char sequence - Should take about 70 minutes... needs improvement, ideas below
             *      
             * Ideas for improvement:
             * 
             *      Use struc with array[] instead of StringBuilder and String  
             *      
             *      Really use diff method other than brute-force/recursion, perhaps neural network Algorithm for graph traversal (parallel)
             * 
             *      Parallelize foreach in RecurseMoves
             *      Maybe: Parallel.ForEach(struc[key], item => RecurseMoves(struc, 0, new StringBuilder(), item.Value));
             * */

            #endregion
        }


        private void RecurseMoves(ConcurrentDictionary<string, List<Key>> struc, int sequenceLength, StringBuilder sb, string key)
        {
            sb.Append(key);

            if (sequenceLength == this.MaxSequenceLength - 1)
            {
                string seq = sb.ToString();
                if (seq.VowelCount() <= 2)
                {
                    // Sequences.Add(seq);
                    SequenceCountInc();
                }
                return;
            }

            foreach (Key k in struc[key])
            {
                this.RecurseMoves(struc, sequenceLength + 1, new StringBuilder(sb.ToString()), k.Value);
            }

        }

        // Thread Safe Increment
        public void SequenceCountInc()
        {
            lock (SequenceCountLock)
            {
                SequenceCount++;
            }
        }

    }
}